#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
struct ListNode
{
    ListNode(int _val,ListNode* tmp)
        :val(_val)
        ,next(tmp)
    {

    }
    int val;
    ListNode* next;

};
//class Solution {
//public:
//    ListNode* reverse(ListNode* head)
//    {
//        ListNode* newhead = new ListNode(0, nullptr);
//        ListNode* cur = head;
//        while (cur)
//        {
//            ListNode* next = cur->next;
//            cur->next = newhead->next;
//            newhead->next = cur;
//            cur = next;
//        }
//        return newhead->next;
//    }
//    void reorderList(ListNode* head) {
//        if (head == nullptr || head->next == nullptr)
//            return;
//        ListNode* slow = head;
//        ListNode* fast = head;
//        ListNode* prev = nullptr;
//        while (fast && fast->next)
//        {
//            prev = slow;
//            slow = slow->next;
//            fast = fast->next->next;
//        }
//        if (prev)
//            prev->next = nullptr;
//        ListNode* newhead = reverse(slow);
//        ListNode* cur1 = head;
//        ListNode* cur2 = newhead;
//        ListNode* head1 = new ListNode(0, nullptr);
//        ListNode* tail1 = head1;
//        while (cur1 || cur2)
//        {
//            if (cur1)
//            {
//                ListNode* next = cur1->next;
//                cur1->next = tail1->next;
//                tail1->next = cur1;
//                tail1 = tail1->next;
//                cur1 = next;
//            }
//            if (cur2)
//            {
//                ListNode* next = cur2->next;
//                cur2->next = tail1->next;
//                tail1->next = cur2;
//                tail1 = tail1->next;
//                cur2 = next;
//            }
//        }
//        delete head1;
//
//    }
//};
#include <queue>
//class Solution {
//public:
//    struct Compare
//    {
//        bool operator()(ListNode* p1, ListNode* p2)
//        {
//            return p1->val > p2->val;
//        }
//
//    };
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        if (lists.size() == 0)
//            return nullptr;
//        if (lists.size() == 1)
//            return lists[0];
//        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
//        //pq.push(lists[0]);
//        for (int i = 0; i < lists.size(); i++)
//        {
//            //if (lists[i]->val < lists[i - 1]->val)
//            if(lists[i])
//                pq.push(lists[i]);
//        }
//        ListNode* ret = new ListNode(0, nullptr);
//        ListNode* tail = ret;
//        while (!pq.empty())
//        {
//            ListNode* tmp = pq.top();
//            ListNode* next = tmp->next;
//            tmp->next = tail->next;
//            tail->next = tmp;
//            tail = tail->next;
//            pq.pop();
//            if (next)
//                pq.push(next);
//        }
//        return ret->next;
//    }
//};

//class Solution {
//public:
//    ListNode* mergesort(vector<ListNode*> lists, int l, int r)
//    {
//        if (l > r)
//            return nullptr;
//        else if (l == r)
//            return lists[l];
//        int mid = (l + r - 1) / 2;
//        ListNode* cur1 = mergesort(lists, l, mid);
//        ListNode* cur2 = mergesort(lists, mid + 1, r);
//        ListNode* ret = new ListNode(0, nullptr);
//        ListNode* tail = ret;
//        while (cur1 || cur2)
//        {
//            if (cur2==nullptr||(cur1 && cur1->val < cur2->val))
//            {
//                ListNode* next = cur1->next;
//                cur1->next = tail->next;
//                tail->next = cur1;
//                cur1 = next;
//                tail = tail->next;
//            }
//            else
//            {
//                ListNode* next = cur2->next;
//                cur2->next = tail->next;
//                tail->next = cur2;
//                cur2 = next;
//                tail = tail->next;
//            }
//        }
//        ListNode* tmp = ret->next;
//        delete ret;
//        return tmp;
//    }
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        return mergesort(lists, 0, lists.size() - 1);
//    }
//};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int count = 0;
        ListNode* newhead = new ListNode(0, nullptr);
        ListNode* newtail = newhead;
        ListNode* cur = head;
        ListNode* prev = newhead;
        while (cur)
        {
            count++;
            cur = cur->next;
        }
        int num = count / k;
        cur = head;
        int count1 = 0;
        int num1 = 0;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = prev->next;
            prev->next = cur;
            cur = next;
            if (newtail->next)
                newtail = newtail->next;
            count1++;
            if (count1 % k == 0)
            {
                num1++;
                prev = newtail;
                if (num1 == num)
                {
                    //
                    newtail->next = cur;
                    break;
                }
            }
        }
        return newhead->next;
    }
};
int main()
{
    ListNode* n1 = new ListNode(1, nullptr);
    ListNode* n2 = new ListNode(2, nullptr);
    ListNode* n3 = new ListNode(3, nullptr);
    ListNode* n4 = new ListNode(4, nullptr);
    ListNode* n5 = new ListNode(5, nullptr);

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
   // vector<ListNode*> lists = { n1,n3 };
  /*  Solution().reorderList(n1);*/
    Solution().reverseKGroup(n1,2);
    return 0;
}